package com.zjsru.plan2025.oneday;

/**
 * 1534. 统计好三元组
 *
 * @Author: cookLee
 * @Date: 2025-04-15
 */
public class CountGoodTriplets {

    /**
     * 主
     * \
     * 0 <= i < j < k < arr.length
     * |arr[i] - arr[j]| <= a
     * |arr[j] - arr[k]| <= b
     * |arr[i] - arr[k]| <= c
     * 其中 |x| 表示 x 的绝对值。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        CountGoodTriplets countGoodTriplets = new CountGoodTriplets();
        countGoodTriplets.countGoodTriplets2(new int[]{3, 0, 1, 1, 9, 7}, 7, 2, 3);
    }

    /**
     * 暴力
     *
     * @param arr arr
     * @param a   a
     * @param b   b
     * @param c   c
     * @return int
     */
    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int len = arr.length;
        int ans = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (Math.abs(arr[i] - arr[j]) <= a) {
                    for (int k = j + 1; k < len; k++) {
                        if (Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c) {
                            ans++;
                        }
                    }
                }
            }
        }
        return ans;
    }

    public int countGoodTriplets2(int[] arr, int a, int b, int c) {
        int len = arr.length;
        int max = 0;
        for (int x : arr) {
            max = Math.max(max, x);
        }
        int[] s = new int[max + 2];
        int ans = 0;
        for (int j = 0; j < len; j++) {
            int y = arr[j];
            for (int k = j + 1; k < len; k++) {
                int z = arr[k];
                if (Math.abs(y - z) > b) {
                    continue;
                }
                //计算满足|x - y| <= a和|x - z| <= c的元素x的范围[l, r]。
                int l = Math.max(Math.max(y - a, z - c), 0);
                int r = Math.min(Math.min(y + a, z + c), max);
                ans += Math.max(s[r + 1] - s[l], 0);
            }
            for (int v = y + 1; v < s.length; v++) {
                s[v]++;
            }
        }
        return ans;
    }

}
